The Biham-Middleton-Levine traffic model is a self-organizing cellular automaton traffic flow model. It consists of a number of cars represented by points on a lattice with a random starting position, where each car may be one of two types: those that only move downwards (shown as blue in this article), and those that only move towards the right (shown as red in this article). The two types of cars take turns to move. During each turn, all the cars for the corresponding type move by one step if possible. It may be considered the two-dimensional analogue of the simpler Rule 184 model. It is possibly the simplest system exhibiting phase transitions and self-organization.[1]
Contents |
The Biham-Middleton-Levine traffic model was first formulated by Ofer Biham, A. Alan Middleton, and Dov Levine in 1992.[2] Biham et al found that as the density of traffic increased, the steady-state flow of traffic suddenly went from smooth flow to a complete jam. In 2005, Raissa D'Souza found that for some traffic densities, there is an intermediate phase characterized by periodic arrangements of jams and smooth flow.[3] In the same year, Alexander Holroyd et al were the first to rigorously prove that for densities close to one, the system will always jam.[4] Later, in 2006, Tim Austin and Itai Benjamini found that for a square lattice of side N, the model will always self-organize to reach full speed if there are fewer than N/2 cars.[5]
The cars are typically placed on a square lattice that is topologically equivalent to a torus: that is, cars that move off the right edge would reappear on the left edge; and cars that move off the top edge would reappear on the bottom edge.
There has also been research in rectangular lattices instead of square ones. For rectangles with coprime dimensions, the periodic structures in the intermediate state are highly regular and ordered, whereas in non-coprime rectangles, the final state has a greater amount of disorder.[1]
Despite the simplicity of the model, it has two highly distinguishable phases — the jammed phase, and the free-flowing phase.[6] For low numbers of cars, the system will usually organize itself to achieve a smooth flow of traffic. In contrast, if there is a high number of cars, the system will become jammed to the extent that no single car will move. Typically, in a square lattice, the transition density is when there are around 32% as many cars as there are possible spaces in the lattice.[7]
The intermediate phase occurs close to the transition density, combining features from both the jammed and free flowing phases. There are principally two intermediate phases — disordered and periodic.[8] It was once thought that the periodic intermediate phase only exists in rectangular lattices with coprime dimensions, although in 2008 it was also observed in square lattices.[1] Disordered intermediate phases, on the other hand, are more frequently observed and tend to dominate densities close to the transition region in square lattices.
Despite the simplicity of the model, rigorous analysis is very nontrivial.[7] There have, however, been mathematical proofs regarding the Biham-Middleton-Levine traffic model. Proofs so far have, however, been restricted to the extremes of traffic density. In 2005, Alexander Holroyd et al proved that for densities close to one, the system will always jam.[9] In 2006, Tim Austin and Itai Benjamini proved that the model will always reach the free-flowing phase if the number of cars is less than half the edge length for a square lattice.[10]
It would be ideal, however, to formulate a rigorous method to predict the end result of any starting position, especially in the intermediate phases.[11] To that end, this model has been the subject of research for several scientists.